package Leetcode.树;

import java.util.Arrays;

/**
 * @ClassName 带因子的二叉树
 * @since: 2023/8/29 09:26
 * @auth: kirito
 * @description:
 * 给出一个含有不重复整数元素的数组 arr ，每个整数 arr[i] 均大于 1。
 *
 * 用这些整数来构建二叉树，每个整数可以使用任意次数。其中：每个非叶结点的值应等于它的两个子结点的值的乘积。
 *
 * 满足条件的二叉树一共有多少个？答案可能很大，返回 对 109 + 7 取余 的结果。
 *
 *
 *
 * 示例 1:
 *
 * 输入: arr = [2, 4]
 * 输出: 3
 * 解释: 可以得到这些二叉树: [2], [4], [4, 2, 2]
 * 示例 2:
 *
 * 输入: arr = [2, 4, 5, 10]
 * 输出: 7
 * 解释: 可以得到这些二叉树: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].
 **/
public class 带因子的二叉树 {
    /**
     * 算法使用动态规划的思想来解决问题。首先对数组进行排序，以便后续处理。然后，使用一个dp数组来存储每个元素作为根节点的二叉树数量。
     *
     * 对于每个元素，初始化其作为根节点的二叉树数量为1。然后，使用双指针left和right从两侧向中间搜索可能的左子节点和右子节点。
     *
     * 如果找到左右子节点使得左子节点乘以右子节点等于当前元素，表示可以构造以当前元素为根节点的二叉树。
     * 此时，根据左右子节点是否相同，计算当前元素作为根节点的二叉树数量：
     *
     * 如果左右子节点不同，将当前元素作为根节点的二叉树数量加上左子树的数量乘以右子树的数量，并乘以2，考虑左右子树的交换情况。
     * 如果左右子节点相同，将当前元素作为根节点的二叉树数量加上左子树的数量，不需要考虑左右子树的交换情况。
     * 在计算完当前元素作为根节点的二叉树数量后，更新结果res，将其加上当前元素作为根节点的二叉树数量，并对结果进行取模操作。
     *
     * 最后返回结果res（需要进行强制类型转换为int）。
     *
     * 请注意，代码中使用了long类型来处理结果和中间计算过程，以避免整数溢出。并且，代码中的取模操作保证了结果在范围内。
     * @param arr
     * @return
     * 动态规划+双指针
     */
    public static int numFactoredBinaryTrees(int[] arr) {
        Arrays.sort(arr); // 对数组进行排序，以便后续处理
        int n = arr.length; // 数组的长度
        long[] dp = new long[n]; // 存储每个元素作为根节点的二叉树数量
        long res = 0, mod = 1000000007; // 结果和取模常量

        // 遍历数组元素
        for (int i = 0; i < n; i++) {
            dp[i] = 1; // 初始化当前元素作为根节点的二叉树数量为1

            // 遍历左子节点
            for (int left = 0, right = i - 1; left <= right; left++) {
                // 使用双指针从两侧向中间搜索可能的右子节点
                while (right >= left && (long) arr[left] * arr[right] > arr[i]) {
                    right--;
                }

                // 如果找到右子节点使得左子节点乘以右子节点等于当前元素
                if (right >= left && (long) arr[left] * arr[right] == arr[i]) {
                    if (right != left) {
                        // 如果左右子节点不同，计算当前元素作为根节点的二叉树数量
                        // 并加上左子树和右子树的数量，乘以2以考虑左右子树的交换
                        dp[i] = (dp[i] + dp[left] * dp[right] * 2) % mod;
                    } else {
                        // 如果左右子节点相同，计算当前元素作为根节点的二叉树数量
                        // 并加上左子树的数量，不需要考虑左右子树的交换
                        dp[i] = (dp[i] + dp[left] * dp[right]) % mod;
                    }
                }
            }

            // 更新结果，加上当前元素作为根节点的二叉树数量
            res = (res + dp[i]) % mod;
        }

        return (int) res; // 返回结果（需要进行强制类型转换）
    }

    public static void main(String[] args) {
        int[] arr = {15,13,22,7,11};
        System.out.println(numFactoredBinaryTrees(arr));
    }
}
